package com.computer.fundamentals.algorithm;

import com.computer.util.Constant;

import java.util.Stack;

/**
 * 最小栈：即栈中元素是有序的【递减】，在很多应用中有奇效
 */
public class MonotonePriorityStack {

    public Stack<int[]> decrementsStack; // 单调栈

    public Stack<int[]> storageStack; // 存储栈

    public int size;

    public MonotonePriorityStack() {
        this.decrementsStack = new Stack<>();
        this.storageStack = new Stack<>();
        this.size = 0;
    }

    /**
     * 压入元素
     */
    public void push(int val) {
        int[] numAndIndex = new int[2];
        numAndIndex[0] = size++;
        numAndIndex[1] = val;
        storageStack.push(numAndIndex);
        if (decrementsStack.isEmpty() || decrementsStack.peek()[1] > val) {
            decrementsStack.push(numAndIndex);
        }
    }

    /**
     * 弹出元素
     */
    public void pop() {
        if (storageStack.isEmpty()) {
            throw new RuntimeException(Constant.STORAGE_STACK_IS_NULL);
        }
        int[] element = storageStack.pop();
        if (element[0] == decrementsStack.peek()[0]) {
            decrementsStack.pop();
        }
        size--;
    }

    /**
     * 获取最小元素
     */
    public int getMin() {
        return decrementsStack.peek()[1];
    }

    /**
     * 获取栈顶元素
     */
    public int top() {
        return storageStack.peek()[1];
    }

    /**
     * 测试
     * 详细测试前往 https://leetcode-cn.com/problems/min-stack/
     */
    public static void main(String[] args) {

        MonotonePriorityStack monotonePriorityStack = new MonotonePriorityStack();
        System.out.println("------------最小栈测试------------");
        monotonePriorityStack.push(-2);
        monotonePriorityStack.push(0);
        monotonePriorityStack.push(-3);
        System.out.println(monotonePriorityStack.getMin());

    }
}